//
// Created by user on 2022/3/3.
//
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class KthLargest1 {
public:
    vector<int> data;
    int k;
    KthLargest(int k, vector<int>& nums) {
        this->k=k;
        this->data=nums;

    }

    int add(int val) {
        data.push_back(val);
        sort(data.begin(), data.end());
        return data[data.size()-k];
    }
};

class KthLargest {
public:
    // 小顶堆
    priority_queue<int, vector<int>, greater<int>> pq;
    int k;
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (int num : nums) {
            add(num);
        }
    }

    // 时间复杂度：O(n)
    int add(int val) {
        if (pq.size() < k) {
            pq.push(val);
        } else if (val > pq.top()) {
            pq.pop();
            pq.push(val);
        }
        return pq.top();
    }
};